package com.topInterview;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 20:51
 */
public class Leecode105_buildTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return process(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }


    public TreeNode process(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        if (l1 > r1) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[l1]);
        if (l1 == r1) {
            return head;
        }
        //找到在中序遍历中的头节点位置
        int findHeadIndexInOrder = l2;
        for (; findHeadIndexInOrder < r2; findHeadIndexInOrder++) {
            if (inorder[findHeadIndexInOrder] == preorder[l1]) {
                break;
            }
        }


        //构建左树，右树
        //左树长度 findHeadIndexInOrder-l2
        head.left = process(preorder, l1 + 1, l1 + findHeadIndexInOrder - l2, inorder, l2, findHeadIndexInOrder - 1);
        head.right = process(preorder, l1 + findHeadIndexInOrder - l2 + 1, r1, inorder, findHeadIndexInOrder + 1, r2);

        return head;

    }
}
